package 我的Java学习_算法基础.day_07;

import java.util.Scanner;

/**
 * @author 挚爱之夕
 * @date 2021/8/21 - 08 - 21 - 21:04
 * @Description: 我的暑假Java学习.day_07
 * @Version: 1.0
 */
public class _119_素数环 {
    public static void main(String[] args) {
        solve();
    }
    static int n ;
    static int[] record ;
    private static void solve(){
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        record = new int[n];
        record[0]=1;
        dfs(n,record,1);
    }

    /**
     * 素数环
     * @param n 1-n自然数
     * @param record 记录已选择的数字
     * @param index 当前record中要填入位置的下标
     */
    private static void dfs(int n,int[] record,int index){
        //填到末尾，还要首尾相加为素数才行
        if(index==n&&isPrime(record[0]+record[n-1])){
            print(record);
            return;
        }
        for (int i = 2; i <= n; i++) {//尝试用每个数字填到index这个位置
            if(check(record,i,index)){//record中没有i这个数，且和上个数之和为素数
                record[index] = i;//试着将i放在cur位置，往前走一步
                dfs(n,record,index+1);
                record[index] = 0;//回溯
            }
        }
    }

    /**
     * 检查record中有没有i这个数，且和上个数之和是否为素数
     * @param record 记录数组
     * @param i 将选数字
     * @param current 当前record中要填入位置的下标
     * @return ture while record don't contain i and i addition a[current-1] is prime
     */
    private static boolean check(int[] record,int i,int current){
        for (int e:record
             ) {
            if(i==e) return false;
        }
        return isPrime(i+record[current-1]);
    }
    private static boolean isPrime(int n){
        if(n==1) return false;
        for(int i = 2;i*i<=n;i++){
            if(n%i==0){
                return false;
            }
        }
        return true;
    }
    private static void print(int[] a){
        for(int i = 0;i<a.length;i++){
            System.out.print(a[i]+(i==a.length-1?"":" "));
        }
        System.out.println();
    }
}
